<?php
/**
 * @title 435. 无重叠区间 - 哈希表 + 前缀和 + 二分查找
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[][] $intervals
     * @return Integer
     */
    function eraseOverlapIntervals($intervals) {
        /**
         * @since 2024-01-10 超时案例55，79008
         */
        // $content = file_get_contents("/tmp/leetcode/435-55.txt");
        // $dataArray = explode("],[", $content);
        // $intervals = [];
        // foreach ($dataArray as $d){
        //     list($num1, $num2) = explode(",", $d);
        //     $intervals[] = [intval($num1), intval($num2)];
        // }
        // return count($intervals);

        /**
         * @since 2024-01-10 记录每个起点的区间数量，min(right)
         */
        $hashArray = [];
        foreach ($intervals as list($left, $right)){
            if(!isset($hashArray[$left])){
                $hashArray[$left] = [$left, $right, 1];
            } else {
                $hashArray[$left][2]++;
                $hashArray[$left][1] = min($hashArray[$left][1], $right);
            }
        }

        /**
         * @since 2024-01-10 按照起点排序
         */
        sort($hashArray);
        $this->intervals = $hashArray;

        /**
         * @since 2024-01-10 前缀和
         */
        $sum = 0;
        $this->sumArray = [];
        foreach ($hashArray as list($left, $right, $count)){
            $sum += $count;
            $this->sumArray[] = $sum;
        }

        /**
         * @since 2024-01-10 避免重复遍历
         */
        $this->dpArray = [];

        /**
         * @return Integer
         */
        return $this->MinDeleteOverlapCount(0);
    }

    /**
     * @title 返回最少删除的区间数目
     * @author start2004
     * @since 2024-01-10 Created
     *
     * @param Integer $s
     * @return Integer
     */
    function MinDeleteOverlapCount($s){
        /**
         * @since 2024-01-10 是否命中缓存
         */
        if(isset($this->dpArray[$s])){
            return $this->dpArray[$s];
        } else {}

        /**
         * @since 2024-01-10 超出数组下标范围
         */
        if($s >= count($this->intervals)){
            return 0;
        } else {}

        /**
         * @since 2024-01-10 下标s的区间[left,minRight, count]
         */
        $minRight = $this->intervals[$s][1];
        $count1 = $this->intervals[$s][2];

        /**
         * @since 2024-01-10 抛弃left起点相同的区间，从下一个区间开始
         */
        $minCount1 = $count1 + $this->MinDeleteOverlapCount($s+1);

        /**
         * @since 2024-01-10 保留[left, minRight]区间，从minRight区间开始
         * @since 2024-01-10 二分查找>=minRight，前缀和求count2
         */
        $left = $s+1;
        $right = count($this->intervals)-1;
        while($left<=$right){
            $m = ($left+$right)>>1;

            /**
             * @since 2024-01-10 找到minRight
             */
            if($this->intervals[$m][0] == $minRight){
                $left = $m;
                break;
            } elseif($this->intervals[$m][0] > $minRight){
                $right = $m-1;
            } else {
                $left = $m+1;
            }
        }

        /**
         * @since 2024-01-10 [s+1, left-1]区间内，元素数量
         */
        $count2 = $this->sumArray[$left-1] - $this->sumArray[$s];
        $minCount2 = ($count1-1) + ($count2) + $this->MinDeleteOverlapCount($left);

        /**
         * @return Integer
         */
        return $this->dpArray[$s] = min($minCount1, $minCount2);
    }
}


/**
 * @url http://127.0.0.1/leetcode/202401/2024.01.10_6.php
 */
$datas = [
    [[[1,4],[1,5],[2,3],[3,4]]], // 2
    // [[[1,4],[2,3],[3,4]]], // 1
    // [[[1,2],[2,3],[3,4],[1,3]]], // 1
    // [[[1,2],[1,2],[1,2]]], // 2
    // [[[1,2],[2,3]]], // 0
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->eraseOverlapIntervals(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
